1. Field of the Invention
The present invention relates generally to a compression method and format of digital data and, more particularly, to a compression method and format of melody data by dictionary coding.
2. Background of the Invention
Existing hand-held communication devices, such as mobile phones and cordless phones, can generally play melody ring tones to announce incoming calls. The melody data may be either pre-stored in the hand-held device or downloaded from a service provider. An efficient compression scheme for the melody data is essential to lower the cost of memory device for storing the melodies or to save bandwidth requirement for downloading the melodies over a band limited channel.
Lossy compression algorithms for compressing sophisticated melody data, like MIDI, have been developed. For example, U.S. Pat. No. 6,525,256 discloses a method of compressing a MIDI file. There is room to further compress the data by lossless schemes. LZ-based compression schemes based on the algorithm presented by Ziv & Lempel in 1977 (LZ77) are widely used for compressing melody data because of its remarkable compression ratio and low complexity of the decompressor. U.S. Pat. Nos. 5,869,782 and 6,476,307 disclose LZ-based compression schemes. LZ77 takes advantage of the repetitive characteristic of the data. The decompression process can be done simply by copying the repeated data from the search window according to an index in the compressed data. Data that is not found in the window is left uncompressed in the compressed data. The decompressed data is then shifted into the search window for the next repetition, and so on. The data is shifted into the window unconditionally without considering the statistical information. Because of limited size of the search window, the first-in data is shifted out unconditionally when the window is full. There are high possibilities that the window is occupied by the useless (non-repetitive) data while the useful (to be repeated) data is banished. To improve the compression ratio, a larger search window should be used and hence more memory would be required by the decompressor.
In 2001, Kwong & Ho presented a concept of statistical Lempel Ziv (SLZ) in IEEE Transactions on Consumer Electronics, Vol. 47, Issue 1, pp. 154-162, February 2001. It is an LZ-like lossless compression algorithm, but statistical information is also taken into consideration to identify the useful data that should be put into the dictionary (search window). It improves the compression ratio compared with LZ77 because more useful data can be kept in the dictionary.
The dictionary can be smaller in size for keeping the useful data and hence less memory is required by the decompressor. Since not all the data has to be shifted into the window, less processing power is required on the decompressor. However, SLZ is a scheme designed for compressing universal data. Kwong & Ho did not teach an efficient method to maintain the dictionary in which the data was in variable lengths. This is a barrier for SLZ to be a practical universal compression scheme.
If the data to be compressed were in form of records in a fixed length, the dictionary is reduced to be a simple first-in-first-out sliding window. Implementation of SLZ becomes practical and all the advantages of SLZ are realized. Melody data is represented by a sequence of musical notes. Each note is represented by a fixed number of bytes that consist of the information of starting time of the note, note duration, note frequency, note velocity, musical instrument playing the note, etc. The inherent characteristics of melody data make SLZ be a suitable scheme for compressing melody data.